import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultEdge;

public class HamPath {
	public UndirectedGraph<String, DefaultEdge> graph;
		
	
	public HamPath(UndirectedGraph<String, DefaultEdge> graph) {
		this.graph = graph;

	}

	// public static UndirectedGraph<String, DefaultEdge> readInGraph(String
	// fileName){
	// UndirectedGraph<String, DefaultEdge> graph = new SimpleGraph<String,
	// DefaultEdge>(DefaultEdge.class);
	// Scanner read = null;
	// int vexNum = 0;
	// try{
	// read = new Scanner(new File(fileName));
	// } catch(FileNotFoundException e){
	// e.printStackTrace();
	// }
	// if(read.hasNextInt()){
	// vexNum = read.nextInt();
	// }
	// read.nextLine();
	// for(int i = 0; i < vexNum; i++){
	// String v = "v" + i;
	// graph.addVertex(v);
	// }
	// String line;
	// String[] lineToken;
	// while(read.hasNextLine()){
	// line = read.nextLine();
	// lineToken = line.split(" ");
	// int size = lineToken.length;
	// String v1 = "v" + lineToken[0];
	// String v2;
	// for(int i = 1; i < size; i++){
	// v2 = "v" + lineToken[i];
	// graph.addEdge(v1, v2);
	// }
	// }
	// read.close();
	// return graph;
	// }

	public boolean isHam() {
		
		for (String vertex : graph.vertexSet()) {
			Set<String> path = new HashSet<String>();
			List<String> hamPath = new ArrayList<String>();
			path.add(vertex);

			if (HamWalk(graph, path, null, hamPath)) {
				return true;
			}
		}
		System.out.println("No Hamiltonian Path.    ");
		return false;

	}

	public boolean HamWalk(UndirectedGraph<String, DefaultEdge> graph,
			Set<String> path, Set<String> addedPath, List<String> hamPath) {
		if (path.size() == graph.vertexSet().size()) {
			System.out.println("Hamiltonian Path: " + hamPath + "  ");
			return true;
		}

		Set<String> newPath = new HashSet<String>();

		if (path.size() == 1) {
			newPath = path;
			for (String vertex : newPath) {
				hamPath.add(vertex);
			}
		} else {
			newPath = addedPath;
		}

		for (String vertex : newPath) {
			Set<DefaultEdge> adjacents = graph.edgesOf(vertex);
			Set<String> addingPath = new HashSet<String>();
			for (DefaultEdge edge : adjacents) {
				if (!vertex.equals(graph.getEdgeSource(edge))) {
					if (!path.contains(graph.getEdgeSource(edge))) {
						addingPath.add(graph.getEdgeSource(edge));
						path.add(graph.getEdgeSource(edge));
						hamPath.add(graph.getEdgeSource(edge));

						HamWalk(graph, path, addingPath, hamPath);
						if (path.size() == graph.vertexSet().size()) {
							return true;
						}
						String removedVertex = hamPath.remove(hamPath.size() - 1);
						path.remove(removedVertex);
						addingPath.remove(removedVertex);
					}
				}
				if (!vertex.equals(graph.getEdgeTarget(edge))) {
					if (!path.contains(graph.getEdgeTarget(edge))) {
						addingPath.add(graph.getEdgeTarget(edge));
						path.add(graph.getEdgeTarget(edge));

						hamPath.add(graph.getEdgeTarget(edge));

						HamWalk(graph, path, addingPath, hamPath);

						if (path.size() == graph.vertexSet().size()) {
							return true;
						}

						String removedVertex = hamPath.remove(hamPath.size() - 1);
						path.remove(removedVertex);
						addingPath.remove(removedVertex);
					}
				}
			}

		}

		return false;

	}

	public List<Set<DefaultEdge>> generateAdjacentVertices() {

		List<Set<DefaultEdge>> adjacents = new ArrayList<Set<DefaultEdge>>();

		for (String vertex : graph.vertexSet()) {
			Set<DefaultEdge> edges = graph.edgesOf(vertex);
			adjacents.add(edges);
		}

		return adjacents;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// UndirectedGraph<String, DefaultEdge> graph =
		// new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
		// String v1 = "v1";
		// String v2 = "v2";
		// String v3 = "v3";
		// String v4 = "v4";
		// String v5 = "v5";
		// String v6 = "v6";
		// graph.addVertex(v1);
		// graph.addVertex(v2);
		// graph.addVertex(v3);
		// graph.addVertex(v4);
		// graph.addVertex(v5);
		// graph.addVertex(v6);
		//
		// graph.addEdge(v3, v2);
		// graph.addEdge(v3, v4);
		// graph.addEdge(v3, v5);
		// graph.addEdge(v1, v2);
		// graph.addEdge(v4, v6);
		// graph.addEdge(v5, v6);

		// System.out.print(a);

//		for (int i = 1; i < 11; i++) {
//
//			if (i < 10) {
//				UndirectedGraph<String, DefaultEdge> graph = ReadGraph
//						.readInGraph("test_case_00" + i + "_input.txt");
//				HamPath test1 = new HamPath(graph);
//				test1.isHam();
//			}
//			else{
//				UndirectedGraph<String, DefaultEdge> graph = ReadGraph
//						.readInGraph("test_case_0" + i + "_input.txt");
//				HamPath test1 = new HamPath(graph);
//				test1.isHam();
//			}
//
//		}
		UndirectedGraph<String, DefaultEdge> graph = ReadGraph
				.readInGraph(args[0]);
		HamPath test1 = new HamPath(graph);
		test1.isHam();
		


	}

}
